/*
https://leetcode-cn.com/problems/delete-columns-to-make-sorted-iii/solution/shan-lie-zao-xu-iii-by-leetcode/
 */
import java.util.Arrays;

public class Solution960 {
    public int minDeletionSize(String[] strs) {
        int[] f=new int[strs[0].length()];
        Arrays.fill(f,1);
        for (int i=0;i<strs[0].length();i++){
            for (int j=0;j<i;j++){
                boolean flag=true;
                for (int k=0;k<strs.length;k++){
                    if (strs[k].charAt(j)>strs[k].charAt(i)){
                        flag=false;
                    }
                }
                if (flag){
                    f[i]=Math.max(f[i],f[j]+1);
                }
            }
        }
        return strs[0].length()-Arrays.stream(f).max().getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(new Solution960().minDeletionSize(new String[]{"babca","bbazb"}));
    }
}
